347. 前 K 个高频元素

Similar Question

Solution Tips

方案一: 哈希表 + 数组排序

哈希表统计所有元素出现的频率, 再排序取第 k 个

let topKFrequent = function(nums, k) {
    let map = new Map(), arr = [...new Set(nums)]
    nums.map((num) => {
        if(map.has(num)) map.set(num, map.get(num)+1)
        else map.set(num, 1)
    })
    
    return arr.sort((a, b) => map.get(b) - map.get(a)).slice(0, k);
};

方案二: 哈希表 + 堆排序

通过 map 数据构建一个前 k 个高频元素小顶堆，小顶堆上的任意节点值都必须小于等于其左右子节点值，即堆顶是最小值。

let topKFrequent = function(nums, k) {
    let map = new Map(), heap = [,]
    nums.map((num) => {
        if(map.has(num)) map.set(num, map.get(num)+1)
        else map.set(num, 1)
    })
    
    // 如果元素数量小于等于 k
    if(map.size <= k) {
        return [...map.keys()]
    }
    
    // 如果元素数量大于 k，遍历map，构建小顶堆
    let i = 0
    map.forEach((value, key) => {
        if(i < k) {
            // 取前k个建堆, 插入堆
            heap.push(key)
            // 原地建立前 k 堆
            if(i === k-1) buildHeap(heap, map, k)
        } else if(map.get(heap[1]) < value) {
            // 替换并堆化
            heap[1] = key
            // 自上而下式堆化第一个元素
            heapify(heap, map, k, 1)
        }
        i++
    })
    // 删除heap中第一个元素
    heap.shift()
    return heap
};

// 原地建堆，从后往前，自上而下式建小顶堆
let buildHeap = (heap, map, k) => {
    if(k === 1) return
    // 从最后一个非叶子节点开始，自上而下式堆化
    for(let i = Math.floor(k/2); i>=1 ; i--) {
        heapify(heap, map, k, i)
    }
}

// 堆化
let heapify = (heap, map, k, i) => {
    // 自上而下式堆化
    while(true) {
        let minIndex = i
        if(2*i <= k && map.get(heap[2*i]) < map.get(heap[i])) {
            minIndex = 2*i
        }
        if(2*i+1 <= k && map.get(heap[2*i+1]) < map.get(heap[minIndex])) {
            minIndex = 2*i+1
        }
        if(minIndex !== i) {
            swap(heap, i, minIndex)
            i = minIndex
        } else {
            break
        }
    }
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

方案三: 桶排序

Loading Question... - 力扣（LeetCode）

方案四: 快速排序

var topKFrequent = function(nums, k) {
    //前k个高频元素
    let hash = new Map();
        //频率统计
    for(let i of nums){
        if(!hash.has(i)) hash.set(i,1);
        else hash.set(i,hash.get(i)+1);
    }
    nums=new Array(hash.size);
    let j=0;
    for(let [key,value] of hash){
        nums[j++]=[key,value];
    }
    getK(nums,0,nums.length-1,k);
    let res=new Array(k);
    for(let i=0;i<k;++i){
        res[i] = nums[i][0];
    }
    return res;
};

//分治   
var getK = function(nums,left,right,k){
    if(left>=right) return ;
    let temp = quikSort(nums,left,right,k);
    if(temp+1==k+left) return ;
    else if(temp+1<k+left){
        getK(nums,temp+1,right,k-(temp+1-left));  //前面的temp+1-left已经符合要求 找剩下的k-(temp+1-left)个最大元素
    } else getK(nums,left,temp-1,k);      //继续找前k个最大元素
    return ;
}

var quikSort = function(nums,left,right){
    if(left>=right) return left;
    let pivot = nums[left];
    let i=left,j=right;
    while(i<j){
        while(nums[j][1]<pivot[1] && i<j) --j;
        nums[i] = nums[j];
        while(nums[i][1]>=pivot[1] && i<j) ++i;
        nums[j] = nums[i];
        if(i==j) nums[i] = pivot;
    }
    return i;
}